package day26;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个整数数组 arr，找到 min(b)的总和，其中 b 的范围为 arr 的每个（连续）子数组。
 *
 * 由于答案可能很大，因此 返回答案模 10^9 + 7 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：arr = [3,1,2,4]
 * 输出：17
 * 解释：
 * 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
 * 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
 * 示例 2：
 *
 * 输入：arr = [11,81,94,43,3]
 * 输出：444
 *
 *
 */
public class Solution1 {
    private static final long MOD = (long) 1e9 + 7;

    public int sumSubarrayMins(int[] arr) {
        Long ans = 0L;
        Deque<Integer> st = new ArrayDeque<>();
        st.push(-1); // 哨兵
        for (int i = 0; i <= arr.length; i++) {
            int x = i<arr.length?arr[i]:-1;
            while (st.size()>1&&arr[st.peek()]>=x){
                int j = st.pop();
                ans+= arr[i]*(j-st.peek())*(i-j);
            }
            st.push(i);
        }
        return (int) (ans % MOD);
    }
}
